This invention relates generally to communication networks and, more particularly, to devices known as bridges, connected to two or more networks and providing a convenient mechanism for transferring data packets between one network and another. Even more particularly, the invention applies to networks that employ a protocol commonly referred to as Carrier Sense Multiple Access with Collision Detection (CSMA/CD). One such network is known as Ethernet.
Under the CSMA/CD rules for access to a network bus or cable, any station wishing to transmit must first "listen" to make sure that the cable is clear before beginning to transmit. All stations on the network have equal priority of access and may begin transmitting as soon as the line is clear and any required inter-packet delay has elapsed. However, if a first station that has started transmitting detects a "collision" with a transmission from another station, the first station continues transmitting for a short time to make sure that all stations wishing to transmit will detect the collision. Every other station detecting the collision also continues to transmit for a short time. Then each station that has detected a collision terminates transmission for some random period of time. The stations involved in the collision select random, and therefore usually different, delay times before trying transmission again.
Partly because of the half-duplex operation of the networks to which the bridge is connected, the bridge has to provide buffer memory for temporarily storing data packets that it is unable to forward immediately onto the destination network. The size of the buffer memory depends on the amount of traffic that the bridge is called upon to handle, the congestion of the destination network, and the accepted level of packet loss. One possible solution to this difficulty is simply to provide a very large amount of buffer memory, so that there is practically always sufficient memory to store a data packet received from one network and destined for another network that is temporarily busy. However, a bridge with a very large buffer memory is costly to implement. For a bridge of lower cost, and smaller buffer memory, some form of congestion control is required, to limit the flow of data packets into the bridge. One way of doing this is, when receiving a data packet through one port of the bridge, to simply "jam" or inhibit data flow from the other port or ports of the bridge. Although this and similar techniques provide for a low-cost bridge implementation, they do not make the most efficient use of the bridge. Clearly, there is much room for improvement in providing traffic congestion control for bridges, and the present invention is directed to this end.
Another aspect of the background to this invention is the manner in which the CSMA/CD protocols select delay times, known as backoff values, when a collision is encountered. The backoff value is expressed as a number of time slots, where one time slot is the network roundtrip delay for the maximum network configuration. After a collision, the normal CSMA/CD protocol calls for the use of randomly selected backoff value between 0 and 1. If there is a second collision, the backoff value is selected from 0 through 3; and after a third collision the backoff value may be between 0 and 7. After subsequent collisions on attempts to retransmit, the backoff value is selected from increasingly greater ranges of numbers, up to 0 to 1,023. Following sixteen attempts to transmit the same packet, it will be discarded, and a new packet will be transmitted, beginning with a backoff value of 0 or 1 following a first collision.
One goal of the present invention is to provide a congestion control mechanism in which the size of the buffer memory is greatly reduced while the packet loss due to the temporary inability of a bridge to accept data remains at an acceptable level. Packet loss is not a totally accurate term, since any "lost" packets will usually be retransmitted upon detection of the loss in some higher level of network protocol.
Another goal of the present invention is to provide a congestion control mechanism that will have little or no effect on the performance of a bridge in which it is installed. In particular, the throughput of the bridge should not be significantly affected by the presence of the congestion control technique, and the latency or transmission delay time should not be significantly increased. The present invention achieves these and other goals.